Optimal Code Motion

Optimal code motion is a compiler optimization technique that aims to reduce redundant calculations, code size, and resource usage by moving computations out of loops (avoiding redundant computation) and into branches (avoiding superfluous computation).

Code motion subsumes many other optimizations such as:

• Common Subexpression Elimination: Computing a subexpression only once and reusing its value instead of recalculating it multiple times.
• Partial Redundancy Elimination: Moving code out of conditionals that is computed in both branches, and moving code into branches that is only used in of the branches.
• Loop Invariant Code Motion: Identifying expressions computed within loops that have the same value from iteration to iteration and moving them out of the loop.

In the project, you will explore a recent development with regard to optimal code motion: Partial Redundancy Elimination in Two Iterative Data Flow Analyses "Knoop et al. proposed the first complete and optimal algorithm, Lazy Code Motion (LCM), which takes four unidirectional data flow analyses. In a recent paper, Roy et al. proposed an algorithm for PRE that uses three iterative data flow analyses. Here, we propose an efficient algorithm for PRE, which takes only two iterative data flow analyses followed by two computation passes over the program."

We will implement the optimal code motion algorithm as part of a optimizing compiler for a toy domain-specific-language using either Lean or Scala.

• Lean is a modern, general-purpose programming language featuring advanced functional programming constructs such as pattern matching, recursion, immutable datastructures, type classes, dependent types and more. At the same time, Lean compiles to C++, featuring easy interopability with low-level libraries where necessary. Let's try it out and see how far we can go :)
• Alternatively, we can try to use Scala instead. Scala is another general-purpose programming language featuring functional concepts such as pattern matching, recursion, immutable datastructures, type classes, but no dependent types. Scala runs on the JVM, featuring easy interopability with the Java ecosystem.